Service discovery protocols can allow devices to find available services with or without intervention of a device user. When service discovery is combined with wireless devices, such as personal digital assistants, personal media players, cell phones, smart phones and tablets, it can provide many interesting possibilities. In some cases, wireless devices can find available services in the near area automatically. Friends in the same area can play games together with smart phones. One characteristic of this proximity based service discovery is that each device can be a service provider as well as a user. As such, it can be beneficial for a first device to inform other devices about available services on the first device at the same relative time the first device discovers service from other devices. There are some existing service discovery protocols such as Wi-Fi Direct, Universal Plug and Play (Upnp) and Bonjour. However, when the number of devices in an area increases, existing service discovery protocols can create high communication traffic volumes and can cause each station to consume a lot of energy monitoring and responding to service discovery requests.